package com.lun.swordtowardoffer2.c06;

import java.util.Stack;

public class LargestRectangleArea {

	//方法一：暴力算法
	public int largestRectangleArea(int[] heights) {
		int maxArea = 0;
		for(int i = 0; i < heights.length; i++) {
			int min = heights[i];
			for(int j = i; j < heights.length; j++) {
				min = Math.min(min, heights[j]);
				int area = min * (j - i + 1);
				maxArea = Math.max(maxArea, area);
			}
		}
		return maxArea;
	}
	
	//方法二：分治
	public int largestRectangleArea2(int[] heights) {
		return largestRectangleArea2(heights, 0, heights.length);
	}
	
	private int largestRectangleArea2(int[] heights, int start, int end) {
		if(start == end)
			return 0;
		
		if(start + 1 == end)
			return heights[start];
		
		int minIndex = start;
		for(int i = start + 1; i < end; i++) {
			if(heights[minIndex] > heights[i]) {
				minIndex = i;
			}
		}
		
		int area = (end - start) * heights[minIndex];
		int left = largestRectangleArea2(heights, start, minIndex);
		int right = largestRectangleArea2(heights, minIndex + 1, end);
		
		return Math.max(Math.max(area, left), right);
	}

	//方法三：单调栈
	public int largestRectangleArea3(int[] heights) {
		Stack<Integer> stack = new Stack<>();
		stack.push(-1);
		int maxArea = 0;
		
		for(int i = 0; i < heights.length; i++) {
			while(stack.peek() != -1 
					&& heights[i] <= heights[stack.peek()]) {
				int height = heights[stack.pop()];
				int width = i - stack.peek() - 1;
				maxArea = Math.max(maxArea, width * height);				
			}
			
			stack.push(i);
		}
		
		while(stack.peek() != -1) {
			int height = heights[stack.pop()];
			int width = heights.length - stack.peek() - 1;
			maxArea = Math.max(maxArea, width * height);				
		}
		
		return maxArea;
	}

}
